//红黑树
#ifndef __REDBLACKTREE__HPP
#define __REDBLACKTREE__HPP

#include"BinaryTree.hpp"

//规则：
//1、根节点是黑的
//2、所有空节点(val=NULL)是黑的
//3、不存在连续两个红节点
//4、从根节点到所有空节点的所有路径的黑节点数量相同

namespace NgSiuKei {

//构造
template<class TheClass>
binary_tree_node<TheClass> *createRedBlackTree(TheClass *data, U_L_L size) {
    if(nullptr == data) {
        return nullptr;
    }
    binary_tree_node<TheClass> *tree = createTree(data[0], (binary_tree_node<TheClass> *)nullptr, (binary_tree_node<TheClass> *)nullptr);
    tree->color = BinaryTreeNodeColorBlack;
    for(U_L_L i=1; i<size; ++i) {
        insertValIntoRedBlackTree(tree, data[i]);
    }
    return tree;
}

//查找
template<class TheClass>
pair<bool, binary_tree_node<TheClass> *> findValFromRedBlackTree(binary_tree_node<TheClass> *tree, const TheClass val) {
    if(nullptr == tree) {
        return make_pair(false, nullptr);
    }
    if(tree->val == val) {
        return make_pair(true, tree);
    }
    else if(tree->val > val) {
        return findValFromRedBlackTree(tree->leftChild, val);
    }
    return findValFromRedBlackTree(tree->rightChild, val);
}

//找最大/小值，flag：false-最大；true-最小
template<class TheClass>
pair<TheClass, binary_tree_node<TheClass> *> getMinOrMaxValFromRedBlackTree(binary_tree_node<TheClass> *tree, bool isFindMin) {
    if(nullptr == tree) {
        throw EXCEPTION_NULL_POINTER;
    }
    if(isFindMin) {
        if(nullptr != tree->leftChild) {
            return getMinOrMaxValFromRedBlackTree(tree->leftChild, isFindMin);
        }
    }
    else {
        if(nullptr != tree->rightChild) {
            return getMinOrMaxValFromRedBlackTree(tree->rightChild, isFindMin);
        }
    }
    return make_pair(tree->val, tree);
}

//使树平衡
template<class TheClass>
void makeRedBlackTreeBalanced(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return;
    }
    makeRedBlackTreeBalanced(tree->leftChild);
    makeRedBlackTreeBalanced(tree->rightChild);

    if(BinaryTreeNodeColorRed == tree->color) {
        if(nullptr == tree->parent) {//规则1：根节点是黑色
            tree->color = BinaryTreeNodeColorBlack;
            return;
        }
        else {//规则3：不存在连续两个红节点
            int type = 0;//记录红子节点（个位）、自己（十位）分别是其父节点的左孩子（1）还是右孩子（2）
            const int L=1, R=2, LL=11, LR=12, RR=22, RL=21;
            //找出红色子节点
            binary_tree_node<TheClass> *childNode = nullptr;
            if(nullptr != tree->leftChild && BinaryTreeNodeColorRed == tree->leftChild->color) {
                type += 1;
                childNode = tree->leftChild;
            }
            if(nullptr != tree->rightChild && BinaryTreeNodeColorRed == tree->rightChild->color) {
                type += 2;
                childNode = tree->rightChild;
            }
            if(0 == type) {
                //没有红色子节点代表没有连续两个红节点
                return;
            }
            //找出自己是父亲的左孩子还是右孩子
            binary_tree_node<TheClass> *parentNode = tree->parent;
            binary_tree_node<TheClass> *brotherNode = nullptr;
            if(parentNode->leftChild == tree) {
                type += 10;
                brotherNode = parentNode->rightChild;
                if(3 == type%10) {
                    type -= 2;
                }
            }
            else {
                type += 20;
                brotherNode = parentNode->leftChild;
                if(3 == type%10) {
                    type -= 1;
                }
            }

            //五种情况需要重新平衡树：
            //1、兄弟节点也是红色
            //2、自己是左孩子，红孩子也是左孩子（LL）
            //3、自己是右孩子，红孩子也是右孩子（RR）
            //4、自己是左孩子，红孩子是右孩子（LR）
            //5、自己是右孩子，红孩子是左孩子（RL）
            if(nullptr != brotherNode && BinaryTreeNodeColorRed == brotherNode->color) {//情况1
                //将父节点变红，将自己和兄弟节点变黑
                parentNode->color = BinaryTreeNodeColorRed;
                tree->color = BinaryTreeNodeColorBlack;
                brotherNode->color = BinaryTreeNodeColorBlack;
            }
            else {//另外四种情况需要翻转，因为发生翻转的节点是父节点，由本节点的parent指针获取，所以不能用leftRotation和rightRotation，这里重新实现一下
                //改颜色
                binary_tree_node<TheClass> *newParentNode = ((LL == type || RR == type)?(tree):(childNode));
                parentNode->color = BinaryTreeNodeColorRed;
                newParentNode->color = BinaryTreeNodeColorBlack;
                //找出父亲是爷爷的左孩子还是右孩子，同时做修改操作
                binary_tree_node<TheClass> *grandparentNode = parentNode->parent;
                if(nullptr != grandparentNode) {
                    if(grandparentNode->leftChild == parentNode) {
                        grandparentNode->leftChild = newParentNode;
                    }
                    else {
                        grandparentNode->rightChild = newParentNode;
                    }
                }
                newParentNode->parent = grandparentNode;
                //旋转操作d
                switch(type) {
                    case LL: {
                        //只右转
                        if(nullptr != tree->rightChild) {
                            tree->rightChild->parent = parentNode;
                        }
                        parentNode->leftChild = tree->rightChild;
                        tree->rightChild = parentNode;
                        parentNode->parent = tree;
                        break;
                    }
                    case RR: {
                        //只左转
                        if(nullptr != tree->leftChild) {
                            tree->leftChild->parent = parentNode;
                        }
                        parentNode->rightChild = tree->leftChild;
                        tree->leftChild = parentNode;
                        parentNode->parent = tree;
                        break;
                    }
                    case LR: {
                        //先左转再右转
                        if(nullptr != childNode->leftChild) {
                            childNode->leftChild->parent = tree;
                        }
                        tree->rightChild = childNode->leftChild;
                        if(nullptr != childNode->rightChild) {
                            childNode->rightChild->parent = parentNode;
                        }
                        parentNode->leftChild = childNode->rightChild;
                        tree->parent = childNode;
                        childNode->leftChild = tree;
                        parentNode->parent = childNode;
                        childNode->rightChild = parentNode;
                        break;
                    }
                    case RL: {
                        //先右转再左转
                        if(nullptr != childNode->leftChild) {
                            childNode->leftChild->parent = parentNode;
                        }
                        parentNode->rightChild = childNode->leftChild;
                        if(nullptr != childNode->rightChild) {
                            childNode->rightChild->parent = tree;
                        }
                        tree->leftChild = childNode->rightChild;
                        parentNode->parent = childNode;
                        childNode->leftChild = parentNode;
                        tree->parent = childNode;
                        childNode->rightChild = tree;
                        break;
                    }
                    default: {
                        break;
                    }
                }
            }
        }
    }
}

//检查树平衡，makeItBalanced-是否检查完让他平衡
template<class TheClass>
bool checkRedBlackTreeBalanced(binary_tree_node<TheClass> *&tree, bool makeTreeBalanced) {
    if(nullptr == tree) {
        return true;
    }
    bool result = (BinaryTreeNodeColorRed == tree->color);
    if(nullptr != tree->leftChild) {
        binary_tree_node<TheClass> *leftChild = tree->leftChild;
        result = result && (BinaryTreeNodeColorRed == tree->leftChild->color) && checkRedBlackTreeBalanced(leftChild, false);
    }
    if(nullptr != tree->rightChild) {
        binary_tree_node<TheClass> *rightChild = tree->rightChild;
        result = result && (BinaryTreeNodeColorRed == tree->rightChild->color) && checkRedBlackTreeBalanced(rightChild, false);
    }

    if(makeTreeBalanced) {
        makeRedBlackTreeBalanced(tree);
        while(nullptr != tree->parent) {
            tree = tree->parent;
        }
    }

    return result;
}

//插入数据
template<class TheClass>
void insertValIntoRedBlackTree(binary_tree_node<TheClass> *&tree, const TheClass val) {
    if(nullptr == tree) {
        return;
    }
    bool isLeft = true;
    if(val < tree->val) {
        if(nullptr == tree->leftChild) {
            isLeft = true;
        }
        else {
            binary_tree_node<TheClass> *leftChild = tree->leftChild;
            insertValIntoRedBlackTree(leftChild, val);
            checkRedBlackTreeBalanced(tree, true);
            return;
        }
    }
    else if(val > tree->val) {
        if(nullptr == tree->rightChild) {
            isLeft = false;
        }
        else {
            binary_tree_node<TheClass> *rightChild = tree->rightChild;
            insertValIntoRedBlackTree(rightChild, val);
            checkRedBlackTreeBalanced(tree, true);
            return;
        }
    }
    else {
        return;
    }

    binary_tree_node<TheClass> *newNode = createTree(val, (binary_tree_node<TheClass> *)nullptr, (binary_tree_node<TheClass> *)nullptr);
    newNode->parent = tree;
    if(isLeft) {
        tree->leftChild = newNode;
    }
    else {
        tree->rightChild = newNode;
    }
    checkRedBlackTreeBalanced(tree, true);
}

//删除
template<class TheClass>
void deleteValFromRedBlackTree(binary_tree_node<TheClass> *&tree, const TheClass val) {
    pair<bool, binary_tree_node<TheClass> *> findValResult = findValFromRedBlackTree(tree, val);
    if(!findValResult.first) {
        return;
    }

    //如果树只有一个节点，就说明这个节点就是待删除节点，直接删除再赋值为空
    if(nullptr == tree->parent && nullptr == tree->leftChild && nullptr == tree->rightChild) {
        delete tree;
        tree = nullptr;
        return;
    }

    //获取目标节点
    binary_tree_node<TheClass> *aimNode = findValResult.second;
    
    //三种情况：
    //1、没有孩子节点，直接删除，更新父节点的孩子节点指针，
    //2、只有一个孩子节点，将父节点的孩子节点指针指向自己的唯一孩子节点
    //3、有两个孩子节点，将左孩子最大值节点或右孩子最小值节点（首选红节点），将两节点值置换，再重新在对应子树执行删除操作
    //变化后需要根据规则改变节点颜色：如果目标节点是黑节点，需要将兄弟节点也变为红节点，父节点变为黑节点

    if(nullptr == aimNode->leftChild || nullptr == aimNode->rightChild) {
        //获取兄弟节点与自己是左还是右兄弟
        binary_tree_node<TheClass> *brotherNode = nullptr;
        bool iAmLeftChild = false;
        if(nullptr != aimNode->parent) {
            if(aimNode == aimNode->parent->leftChild) {
                iAmLeftChild = true;
                brotherNode = aimNode->parent->rightChild;
            }
            else {
                iAmLeftChild = false;
                brotherNode = aimNode->parent->leftChild;
            }

            //改变颜色
            if(BinaryTreeNodeColorBlack == aimNode->color) {
                aimNode->parent->color = BinaryTreeNodeColorBlack;
                if(nullptr != brotherNode) {
                    brotherNode->color = BinaryTreeNodeColorRed;
                }
            }
        }

        binary_tree_node<TheClass> *childNode = nullptr;
        if(nullptr != aimNode->leftChild) {
            childNode = aimNode->leftChild;
        }
        if(nullptr != aimNode->rightChild) {
            childNode = aimNode->rightChild;
        }

        if(nullptr == childNode) {//情况1
            if(nullptr != aimNode->parent) {
                if(iAmLeftChild) {
                    aimNode->parent->leftChild = nullptr;
                }
                else {
                    aimNode->parent->rightChild = nullptr;
                }
            }
            else {
                tree = nullptr;
            }
        }
        else {//情况2
            if(nullptr != aimNode->parent) {
                if(iAmLeftChild) {
                    aimNode->parent->leftChild = childNode;
                }
                else {
                    aimNode->parent->rightChild = childNode;
                }
                childNode->parent = aimNode->parent;
            }
            else {
                tree = childNode;
                childNode->parent = nullptr;
            }
        }

        //删除节点
        delete aimNode;
        aimNode = nullptr;

        checkRedBlackTreeBalanced(tree, true);
    }
    else {//情况3
        //获取左孩子最大值节点和右孩子最小值节点
        pair<TheClass, binary_tree_node<TheClass> *> pairLeftChildMaxValNode = getMinOrMaxValFromRedBlackTree(aimNode->leftChild, false);
        pair<TheClass, binary_tree_node<TheClass> *> pairRightChildMinValNode = getMinOrMaxValFromRedBlackTree(aimNode->rightChild, true);
        TheClass leftChildMaxVal = pairLeftChildMaxValNode.first;
        TheClass rightChildMinVal = pairRightChildMinValNode.first;
        binary_tree_node<TheClass> *leftChildMaxValNode = pairLeftChildMaxValNode.second;
        binary_tree_node<TheClass> *rightChildMinValNode = pairRightChildMinValNode.second;

        //默认使用左孩子最大值节点，除非右孩子最小值节点是红节点
        if(BinaryTreeNodeColorRed == rightChildMinValNode->color) {
            aimNode->val = rightChildMinVal;
            deleteValFromRedBlackTree(rightChildMinValNode, rightChildMinVal);
        }
        else {
            aimNode->val = leftChildMaxVal;
            deleteValFromRedBlackTree(leftChildMaxValNode, leftChildMaxVal);
        }
    }
    checkRedBlackTreeBalanced(tree, true);
}

//打印
template<class TheClass>
void printRedBlackTree(binary_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        cout << "[null]" << endl;
        return;
    }
    
    if(nullptr == tree->parent) {
        cout << "[root]-";
    }
    cout << '[' << tree->val << '-' << ((BinaryTreeNodeColorBlack == tree->color)?("black"):("red")) << ']' << endl;
    if(nullptr != tree->leftChild) {
        cout << "[L-" << tree->val << "]-"; printRedBlackTree(tree->leftChild);
    }
    if(nullptr != tree->rightChild) {
        cout << "[R-" << tree->val << "]-"; printRedBlackTree(tree->rightChild);
    }
}

};

#endif